package com.wenyl.heap;

import lombok.Data;


/**
 * @author Swimming Dragon
 * @description: 最小根堆
 * @date 2024年11月01日 10:38
 */
@Data
public class MinRootHeap{
    private Integer[] heap;
    // 堆的初始长度
    private int length = 16;
    // 当前堆中元素的数量
    private int size;

    public MinRootHeap(){
        heap = new Integer[length];
        size = 0;
    }

    public boolean isEmpty(){
        // 检查堆是否为空
        return size == 0;
    }

    /**
     * 将元素 x 添加到堆中，自底向上遍历排序
     * 时间复杂度: O(log n)，因为在最坏情况下需要向上遍历堆的高度
     */
    public void offer(int x){
        // 新元素的索引
        int index = size;
        // 检查堆是否已满
        if(index >= length){
            System.out.println("满了");
            return;
        }
        // 自底向上调整堆
        while(index > 0){
            // 计算父节点索引
            int parentIndex = (index - 1) >>> 1;
            // 获取父节点的值
            int parent = heap[parentIndex];
            // 如果父节点小于等于新元素，停止调整
            if(parent <= x){
                break;
            }
            // 将父节点下移
            heap[index] = parent;
            // 更新当前索引为父节点索引
            index = parentIndex;
        }
        // 将新元素放入堆中
        heap[index] = x;
        size++; // 增加堆的大小
    }

    public int poll(){
        if(size == 0){
            System.out.println("队列为空");
            return -1;
        }
        // 保存堆顶元素
        int ret = heap[0];
        // 只有一个元素直接删除
        if(size == 1){
            heap[0] = null;
            size--;
            return ret;
        }
        // 把最后一个元素放到堆顶，然后将最后一个元素置空
        int lastIndex = --size;
        int lastElement = heap[lastIndex];
        heap[size] = null;
        // 从下标0开始，对最后一个元素lastElement进行自顶向下的比较操作,找到最后一个元素此时应该在哪个位置
        int targetIndex = 0;
        // 根据最后一个元素的下标，计算出最后一个非叶子节点的元素下标
        int half = lastIndex >>> 1;
        while(targetIndex < half){
            int leftChildIndex = (targetIndex << 1) + 1;
            int rightChildIndex = leftChildIndex + 1;
            // 两个孩子最小值下标
            int minIndex;
            // 存在左右两个兄弟
            if(rightChildIndex < lastIndex){
                if(heap[leftChildIndex] <= heap[rightChildIndex]){
                    minIndex = leftChildIndex;
                }else{
                    minIndex = rightChildIndex;
                }
            }
            // 只存在左孩子,这里只有一个孩子是因为我们把最后一个叶子节点放到了数组第一个位置
            else{
                if(lastElement <= heap[leftChildIndex]){
                    break; // 如果最后一个元素小于等于左孩子，停止调整
                }else{
                    minIndex = leftChildIndex;
                }
            }
            if(lastElement <= heap[minIndex]){
                break; // 如果最后一个元素小于等于最小孩子，停止调整
            }else{
                heap[targetIndex] = heap[minIndex];
                targetIndex = minIndex;
            }
        }
        heap[targetIndex] = lastElement;
        return ret;
    }
}
